package com.yangzhe.algorithm.c036;

// 二叉树按层序列化和反序列化
// 测试链接 : https://leetcode.cn/problems/serialize-and-deserialize-binary-tree/
public class Code06_LevelorderSerializeAndDeserialize_LeetCode {

    // 不提交这个类
    public static class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int v) {
            val = v;
        }
    }

    // 提交这个类
    // 按层序列化
    public class Codec {

        TreeNode[] queue = new TreeNode[10001];

        public String serialize(TreeNode root) {
            if (root == null) {
                return null;
            }
            StringBuilder sb = new StringBuilder("");
            int l = 0, r = 0;
            sb.append(root.val + ",");
            queue[r++] = root;

            while (l != r) {
                TreeNode treeNode = queue[l++];

                if (treeNode.left != null) {
                    queue[r++] = treeNode.left;
                    sb.append(treeNode.left.val + ",");
                } else {
                    sb.append("#,");
                }

                if (treeNode.right != null) {
                    queue[r++] = treeNode.right;
                    sb.append(treeNode.right.val + ",");
                } else {
                    sb.append("#,");
                }
            }

            return sb.toString();
        }

        public TreeNode deserialize(String data) {
            if (data == null || data.isEmpty()) {
                return null;
            }

            String[] nodes = data.split(",");

            int l = 0, r = 0, cur = 0;
            TreeNode root = generateNode(nodes[cur++]);
            queue[r++] = root;
            while (l < r) {
                TreeNode node = queue[l++];
                node.left = generateNode(nodes[cur++]);
                if (node.left != null) {
                    queue[r++] = node.left;
                }

                node.right = generateNode(nodes[cur++]);
                if (node.right != null) {
                    queue[r++] = node.right;
                }
            }

            return root;
        }

        public TreeNode generateNode(String val) {
            if (val.equals("#")) {
                return null;
            } else {
                TreeNode node = new TreeNode(Integer.valueOf(val));
                return node;
            }
        }
    }

}
